1. Field of the Invention
The present invention relates, in general, to error correction codes for communication channels such as read channels for hard disk drive (HDD) systems and magneto resistive data storage devices and systems, and, more particularly, to a communication channel with an iterative error correction loop implementing a stopping criterion mechanism that significantly reduces the number of iterations, such as by generating a stopping criterion using the Reed-Solomon error location polynomial that is used to determine whether additional iterations are to be performed.
2. Relevant Background
The demand for improved data storage techniques and systems continues to rapidly grow. Hard disk drives utilizing magneto resistive (MR) heads to read and write data onto one or more spinning magnetic platters or disks are one of the more important and wide spread devices in the data storage industry. Hard disk drives may be used in many applications, including enterprise computer systems, personal computers, set top boxes, audio, video, or television applications, and many other large and small computer devices. Many applications are still being developed, and the uses for hard disk drives are expected to increase.
Hard disk drives store binary encoded information as regions of magnetic flux on a media having a magnetic surface coating. It is desirable that these magnetic regions be encoded on the disk as densely as practical, so that a maximum amount of information may be stored. Disk and tape drive suppliers continue to increase areal densities, or the number of data bits per square inch, to meet the increasing demand for storage at competitive pricing. An ongoing challenge is that the increasing areal density requires the write mechanism to produce smaller recorded patterns which are more difficult for the read mechanism (or read channel) to read and decode without (or with acceptable) error.
More generally, error-correcting codes are often used in the communication or transfer of digital information over noisy (or error producing) channels, such as may be found in hard disk drives, compact disc systems, computer memories, and the like. For example, a message may first be given by a source to an encoder that turns the message into a codeword, i.e., a string of letters from some alphabet, chosen according to the code used (such as a Reed-Solomon (RS) code. The encoded message is then sent through the channel where it may be subjected to noise and, as a result, altered. For example, in a hard disk drive, digital information is encoded prior to writing on a disk surface and is then read in the encoded form, with some noise being experienced in the “channel” that includes the disk, the read/write heads, and transmission media. When this message is read or received at a decoder belonging to a receiver, it is decoded and as necessary, corrected for introduced errors with an error-correcting code.
A present challenge in decoding is how best to accurately decode messages while controlling the complexity and space for corresponding hardware. For example, an error-correcting code that requires numerous iterations may be undesirable as requiring excessive real estate on as integrated circuit (IC) or reconfigurable system-on-chip to implement. Turbo codes have been developed that provide a system of parallel concatenated recursive convolutional error-correction codes that are separated by random interleavers (i.e., devices that output a permuted version of its input symbols) in the encoder. Decoders are configured with a network of modules to provide iterative decoding, i.e., with counterparts of the modules in the transmitter and its encoder. Turbo encoders and decoders are key elements in many communication systems and perform date reception with few errors. The basis of turbo coding can be thought of as introducing redundancy in the data to be transmitted through a channel that helps to recover the original data from the received data. A significant concern is the computation complexity of the iterative decoder, and there are continuing efforts to find a class of decoding algorithms that result in less complex hardware implementation, and specifically, there has been some efforts to at least provide a stopping criterion for use in determining the number of iterations that occur in the decoder, such as by providing a fixed or explicit number or threshold for iterations in the error-correcting loop. These efforts have not been entirely successful.
More specifically, recent developments in iterative decoding techniques based on turbo codes promise substantial gains over conventionally used partial response maximum likelihood detection methods in magnetic disk drive read channels. The main difficulties in incorporating iterative decoding systems in existing commercial products and similar designs are the complexity and the size of the decoder. Such iterative decoding systems have to be capable of performing at least two to five iterations in order to demonstrate significant coding gains. Hence, for an implementation to perform a fixed number of iterations (“ν”), the hardware has to be duplicated ν times or the effective throughput has to be reduced by ν times. Neither of these implementation options appears acceptable given current trends in magnetic storage applications.
A multitude of proposals have been suggested for providing stopping criterion to provide a more practical iterative decoder implementation. One proposal involves the obvious solution of ending further iterations when a valid codeword has been determined. However, aside from the additional hardware that would be required to determine the validity of the codeword, such a stopping criterion leads to overcorrecting of the code. For example, by design, a Reed-Solomon decoder provided at the output of an iterative decoder system is capable of correcting erroneous bits when there are less than a particular number (“t”) of error symbols. Hence, the output of the iterative decoder does not need to strictly error free as called for in this proposed implementation. Further, simple parity checking of convolutional codes is not an effective method as a large number of 2-bit and 4-bit error events cannot be detected.
Other proposed solutions generally employ some form of metric that monitors the evolution of Log Likelihood Ration (LLR) values, with LLR being the probability that the received data bit is a “0” divided by the probability that the received data bit is a “1.” A comparison with a preset threshold that is selected based on either the absolute value, the polarity (i.e., signs), or mean of the LLR values determines if further iterations are required during decoding. Unfortunately, the evaluation of these metrics requires substantial amounts of additional hardware. Further, the threshold values are set through empirical methods, which impairs the theoretical analysis of error-correction performance at very low bit error rates (BERs). In general, stopping criteria that are based on a preset threshold need to be sufficiently conservative in order to avoid premature passing of an uncorrectable error to the outer Reed-Solomon decoder. Premature implies that the error would have become correctable by the Reed Solomon decoder had there been further iteration of the inner decoder. On the other hand, an overly conservative threshold may result in a high number of false alarms, effectively increasing the number of required iterations. These opposing factors present a difficult tradeoff, which is exacerbated in the event of applications requiring very low bit-error rates, such as a magnetic recording channel.
Hence, a need exists for an iterative decoder for use in communication channels, such as read channels of HDD systems and devices, that implements a stopping criterion (or stopping criterion generator or mechanism) to effective select a number of iterations performed during error correction by the decoder. Preferably, such a stopping criterion is selected such that its implementation can be performed with acceptable (e.g., negligible) added hardware in the decoder or communication channel while providing performance similar to or even identical to performance of an iterative loop system that performs the maximum number of iterations every time.